/*
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]
*/

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> >result;
        if (n) {
            vector<int> board(n,0);
            placeQueen(0, board, result);
        }
        return result;
    }
private:
    void placeQueen(int row, vector<int> &board, vector<vector<string> > &result) {
        if (row == board.size()) {
            printBoard(board, result);  // complete answer
        } else {
            // try to place queen on each column    
            for (int col=0; col<board.size(); col++) {
                if (checkValid(row, col, board)) {
                    board[row] = col;   // place queen
                    placeQueen(row+1, board, result);
                }
             }
        }
    }
    bool checkValid(int row, int col, vector<int> &board) {
        for (int i=0; i < row; i++) {
            if (col == board[i]) return false;                // check column
            if ((row-i) == abs(col-board[i])) return false;   // check diagonal
        }
        return true;
    }
    void printBoard(vector<int> &board, vector<vector<string> > &result) {
        int n = board.size();
        vector<string> str(n, "");
        for (int i = 0; i < n; i++) {
            int qpos = board[i];
            if (qpos) str[i].append(qpos, '.');
            str[i].append(1, 'Q');
            if (qpos < n-1) str[i].append(n-1-qpos, '.');
        }
        result.push_back(str);
    }
};
